package com.moyoutian.sort;

import com.moyoutian.utils.ArrayUtils;

/**
 * 选择排序练习
 * 思想概述：
 * 选择（查找）出当前数组中最大或最小的的放到最后或者最前面，然后找到除了最后一个的以外最大的放到次后以此类推。
 */
public class SelectSort {

    public static void main(String[] args) {
//        int[] ints = {5, 1, 3, 2, 0, 9, 7, 8, 11, 23, 4};
        int[] ints = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
//         int[] ints = {0, 1, 2, 3, 4, 5, 6, 7, 8,9 };
        ArrayUtils.printArray("原始", ints);
        sortRecursion(ints, 0, ints.length - 1);
        ArrayUtils.printArray("结果", ints);
    }

    /**
     * 出当前数组中最大的值的下标
     *
     * @param ints 数组
     * @param l    左边界
     * @param r    又边界
     */
    public static int selectMaxIndex(int[] ints, int l, int r) {
        if (l > r) return -1;
        int max = l;
        for (int i = 0; l <= i && i <= r; i++) {
            if (ints[i] > ints[max]) {
                max = i;
            }
        }
        return max;
    }

    /**
     * 选择普通版
     *
     * @param ints 待排序数组
     */
    public static void sort(int[] ints) {
        for (int i = ints.length - 1; i > 0; i--) {
            int max_index = selectMaxIndex(ints, 0, i);
            ArrayUtils.swap(ints, max_index, i);
            ArrayUtils.printArray("sortPro第" + i + "次", ints);
        }
    }

    /**
     * 选择排序递归版
     *
     * @param ints 待排序数组
     */
    public static void sortRecursion(int[] ints, int l, int r) {
        ArrayUtils.swap(ints, selectMaxIndex(ints, l, r), r);
        ArrayUtils.printArray("sortPro", ints);
        if (l < r) {
            sortRecursion(ints, 0, r -= 1);
        }
    }


    /**
     * 选择双头并进，这个算法时间复杂度并没有优化。只是提供思想。
     * n*(n/2)
     *
     * @param ints 待排序数组
     */
    public static void sortToHeader(int[] ints) {
        for (int i = 0; i < ints.length; i++) {
            //是否换位标志
            //左边界
            int l = i;
            //右边界
            int r = ints.length - i - 1;
            // 初始最大值下标
            int max = r;
            // 初始最小值下标
            int min = l;
            int n = l;
            while (n <= r) {
                // 记录最大值的坐标
                if (ints[n] > ints[max]) {
                    max = n;
                }
                // 记录最小值的坐标
                if (ints[n] < ints[min]) {
                    min = n;
                }
                n++;
            }
            // 如果最大值和最小值刚刚好位于两边就拿它俩做交换
            if (max == l & min == r) {
                ArrayUtils.swap(ints, max, min);
            } else {
                ArrayUtils.swap(ints, max, r);
                ArrayUtils.swap(ints, min, l);
            }
            ArrayUtils.printArray("sortPro第" + (i + 1) + "次", ints);
            if (r <= l) return;
        }
    }
}
